package com.soul.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void sort(int[] a) {
        int len = 1;
        //创建一个临时数组
        int[] t = Arrays.copyOf(a, a.length);
        while (a.length > len) {
            //将数组中的元素拆分成两段并排序，直至无法拆分，将有序子序列合并为有序序列
            msort(a, t, a.length, len);
            len *= 2;
        }
    }

    /**
     * 归并数组
     * 假设左右两列挨着，则左边终点为右边起点减去1
     * @param a  原数组
     * @param t  临时数组
     * @param l  左边起点，存放起点位置
     * @param r  右边起点
     * @param re 右边终点
     */
    private static void merge(int[] a, int[] t, int l, int r, int re) {
        int le = r - 1;
        int tmp = l;
        int n = re - l + 1;
        while (l <= le && r <= re) {
            if (a[l] <= a[r]) {
                t[tmp++] = a[l++];
            } else {
                t[tmp++] = a[r++];
            }
        }
        while (l <= le) {
            t[tmp++] = a[l++];
        }
        while (r <= re) {
            t[tmp++] = a[r++];
        }
        for (int i = 0; i < n; i++, re--) {
            a[re] = t[re];
        }
    }

    private static void msort(int[] a, int[] t, int n, int len) {
        for (int i = 0; i + len <= n; i += 2 * len) {
            int re = i + 2 * len - 1;
            if (re > n - 1) {
                re = n - 1;
            }
            merge(a, t, i, i + len, re);
        }
    }

}
